#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

vector<int> p;

bool prime(int k)
{
	if (k <= 1) return false;
	int sq = (int) sqrt(k);
	
	for (int i = 2; i <= sq; i++)
		if (k % i == 0) return false;
		
	return true;
}

int m, n;

int main()
{
	for (int i = 2; i <= 80; i++)
		if (prime(i)) p.push_back(i);

	int ntest;
	cin >> ntest;

	for (int test = 1; test <= ntest; test++)
	{
		int result = 1000000000;

		cin >> m >> n;
		for (int i = 0; i < (int)p.size(); i++)
		{
			if (m < p[i]) break;

			if (m % p[i] == 0)
 			{
				int ri = 0;
				while (m % p[i] == 0)
				{
					m /= p[i];
					ri++;
				}

				int k = n, sum = 0;
				while (k > 0)
				{
					sum += k/p[i];
					k /= p[i];
				}
					
				result = min(result, (int) ((double) sum / ri));
			}
		}

		if (m > 1) 
		{
			int k = n, sum = 0;
			while (k > 0)
			{
				sum += k/m;
				k /= m;
			}
			result = min(result, (int) ((double) sum));
		}

		cout << "Case " << test << ":" << endl;
		if (result == 0) cout << "Impossible to divide" << endl;
		else cout << result << endl;
	}

	return 0;	
}
